import java.util.HashMap;
import java.util.Map;

public class Test {
    // https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/submissions/677572971/
    public String modifyString(String s) {
        char[] arr=s.toCharArray();
        for(int i=0;i<arr.length;i++) {
            if(arr[i]=='?') {
                for(char ch='a';ch<='z';ch++) {
                    if((i==0 || ch!=arr[i-1]) && (i==arr.length-1 || ch!=arr[i+1])) {
                        arr[i]=ch;
                        break;
                    }
                }
            }
        }
        return String.valueOf(arr);
    }

    // https://leetcode.cn/problems/teemo-attacking/submissions/677576538/
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret=0;
        for(int i=0;i<timeSeries.length-1;i++) {
            int tmp=timeSeries[i+1]-timeSeries[i];
            if(tmp>=duration) ret+=duration;
            else ret+=tmp;
        }
        ret+=duration;
        return ret;
    }

    // 老师的思路 https://leetcode.cn/problems/zigzag-conversion/
    public String convert(String s,int numRows) {
        // 处理边界情况,若numRows==1,一定会进入for循环,d=0,递增语句是 i+=0, 就死循环了
        if(numRows==1) return s;
        int d=2*numRows-2;
        int n=s.length();
        StringBuilder ret=new StringBuilder();
        // 先处理第一行
        for(int i=0;i<n;i+=d) {
            ret.append(s.charAt(i));
        }
        // 处理中间行,k是行号
        for(int k=1;k<numRows-1;k++) {
            for(int i=k,j=d-k;i<n || j<n;i+=d,j+=d) {
                // 先添加i位置的元素,再添加j的元素.但是添加之前,需要先判断i,j是否越界
                if(i<n) ret.append(s.charAt(i));
                if(j<n) ret.append(s.charAt(j));
            }
        }
        // 处理最后一行
        for(int i=numRows-1;i<n;i++) {
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }
    // 我自己的思路
    public String convert2(String s, int numRows) {
        if(numRows==1) return s;

        int n=s.length();
        char[] ret=new char[n];
        int x=0;
        int d=2*numRows-2;
        for(int i=0;i<numRows;i++) {
            int j=i;
            if(i==0 || i==numRows-1) {      // 处理第一行和最后一行
                while(j<ret.length) {
                    ret[x++]=s.charAt(j);
                    j+=d;
                }
            }
            else {
                // 中间的行
                int tmp1=i;
                int tmp2=d-i;
                while(tmp1<ret.length || tmp2<ret.length) {
                    if(tmp1<ret.length) ret[x++]=s.charAt(tmp1);
                    if(tmp2<ret.length) ret[x++]=s.charAt(tmp2);
                    tmp1+=d;
                    tmp2+=d;
                }
            }
        }
        return String.valueOf(ret);
    }

    // https://leetcode.cn/problems/count-and-say/
    // 我的思路(和老师的思路一致)
    public String countAndSay(int n) {
        StringBuilder tmp = new StringBuilder();
        tmp.append('1' + "");
        for (int i = 2; i <= n; i++) {
            StringBuilder ret = new StringBuilder();
            for (int left = 0, right = 0; right < tmp.length();) {
                char chL = tmp.charAt(left);
                // 在循环条件中检查边界
                while (right < tmp.length() && tmp.charAt(right) == chL) {
                    right++;
                }
                String count = (right - left) + "";
                ret.append(count);
                ret.append(chL);
                left = right;
            }
            tmp = ret;
        }
        return tmp.toString();
    }


    // 数青蛙 https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/
    // 我自己的解法
    public int minNumberOfFrogs(String croakOfFrogs) {
        Map<Character,Integer> hash=new HashMap<Character,Integer>();// 存储每个字符的出现情况
        char[] arr=croakOfFrogs.toCharArray();
        for(int i=0;i<arr.length;i++) {
            if(arr[i]=='r') {
                // 找 c
                int tmpC=hash.getOrDefault('c',0);
                int tmpR=hash.getOrDefault('r',0);
                if(tmpC!=0) {
                    hash.put('c',tmpC-1);
                    hash.put('r',tmpR+1);
                } else return -1;
            } else if(arr[i]=='o') {
                // 找 r
                int tmpR=hash.getOrDefault('r',0);
                int tmpO=hash.getOrDefault('o',0);
                if(tmpR!=0) {
                    hash.put('r',tmpR-1);
                    hash.put('o',tmpO+1);
                } else return -1;
            } else if(arr[i]=='a') {
                // 找 o
                int tmpO=hash.getOrDefault('o',0);
                int tmpA=hash.getOrDefault('a',0);
                if(tmpO!=0) {
                    hash.put('o',tmpO-1);
                    hash.put('a',tmpA+1);
                } else return -1;
            } else if(arr[i]=='k') {
                // 找 a
                int tmpA=hash.getOrDefault('a',0);
                int tmpK=hash.getOrDefault('k',0);
                if(tmpA!=0) {
                    hash.put('a',tmpA-1);
                    hash.put('k',tmpK+1);
                } else return -1;
            } else if(arr[i]=='c') {
                int tmpK=hash.getOrDefault('k',0);
                int tmpC=hash.getOrDefault('c',0);
                if(tmpK!=0) {
                    hash.put('k',tmpK-1);
                    hash.put('c',tmpC+1);
                } else {
                    hash.put('c',tmpC+1);
                }
            }
        }
        // 最后判断哈希表中除k以外字符的情况
        int tmpC=hash.getOrDefault('c',0);
        int tmpR=hash.getOrDefault('r',0);
        int tmpO=hash.getOrDefault('o',0);
        int tmpA=hash.getOrDefault('a',0);
        int tmpK=hash.getOrDefault('k',0);
        if(tmpC!=0 || tmpR!=0 || tmpO!=0 || tmpA!=0) return -1;
        else return tmpK;
    }
    // 老师的解法(更通用)
    public int minNumberOfFrogs2(String croakOfFrogs) {
        String t="croak";
        int n=t.length();
        char[] arr=croakOfFrogs.toCharArray();
        int[] hash=new int[n];// 用数组模拟哈希表.存放的是每个字符的出现情况
         Map<Character,Integer> index=new HashMap<>();// 将字符和它的下标绑定存储在哈希表中
         for(int i=0;i<n;i++) {
             index.put(t.charAt(i),i);// 构建 字符:下标 的映射
         }

         for(char ch:arr) {
             if(ch==t.charAt(0)) {  // 处理叫声字符串的第一个字符
                 if(hash[n-1]!=0) {
                     hash[n-1]--;
                 }
                 hash[0]++;
             } else {       // 处理叫声字符串的其他字符
                 int i=index.get(ch);
                 if(hash[i-1]==0) return -1;
                 hash[i-1]--;
                 hash[i]++;
             }
         }
        for(int i=0;i<n-1;i++) {
            if(hash[i]!=0) return -1;
        }
        return hash[n-1];
    }



}
